package com.promote.algorithm;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName NextGreaterElements
 * Description 下一个更大元素--力扣  单调栈 + 循环数组
 * @Author LiZiHao
 * Date 2021/10/19 17:39
 * @Version 1.0
 **/
public class NextGreaterElements {

    public static int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] ret = new int[length];
        //填充数组
        Arrays.fill(ret,-1);

        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < length * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[ i%length]) {
                ret[stack.pop()] = nums[i%length];
            }
            stack.push(i%length);
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,1};
        int[] ints = nextGreaterElements(nums);
        System.out.println(ints);
    }
}
